package edu.whu.rose.clock.kps.algorithm.cbes;

import java.io.FileWriter;
import java.io.IOException;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import edu.whu.rose.clock.kps.algorithm.SearchAlgorithm;
import edu.whu.rose.clock.kps.algorithm.banks1.SPVertex;
import edu.whu.rose.clock.kps.datastruct.PrimitiveMatchedSubgraph;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class MyBestAlgorithm extends SearchAlgorithm {

	private int groupNum;
	private GraphMatrix graph;

	private PrimitiveMatchedSubgraph[] matched_subgraphs;

	private GroupIteratorInFullGraph[] iterators;
	private boolean[] groupEmpty;
	
	private long startTime;
	
	private FileWriter fw;
	
	public long initTime;
	public long firstkTime;
	public long topkTime;
	
	public boolean needPrint;
	public int[] initVertexNums;

	public MyBestAlgorithm(GraphMatrix graph,
			PrimitiveMatchedSubgraph[] matched_subgraphs, FileWriter fw) {
		this.graph = graph;
		groupNum = matched_subgraphs[0].groupNum();
		groupEmpty = new boolean[groupNum];
		this.matched_subgraphs = matched_subgraphs;
		this.fw = fw;
	}

	public void init() {
		startTime = new Date().getTime();
		initTime = 0l;
		firstkTime = 0l;
		topkTime = 0l;
		
		iterators = new GroupIteratorInFullGraph[groupNum];
		
		SequentialIntArray vertexes = new SequentialIntArray(graph.getN());
		
		for (int i = 0; i < matched_subgraphs.length; i++) {
			int[] subVertexes = matched_subgraphs[i].getSubgraph().getVertexes();
			for (int j = 0; j < subVertexes.length; j++) {
				vertexes.insert(subVertexes[j]);
			}
		}
		
		try {
			initVertexNums = new int[groupNum];
			for (int i = 0; i < groupNum; i++) {
				SequentialIntArray initVertexes = new SequentialIntArray();
				for (int j = 0; j < matched_subgraphs.length; j++) {
					int[] subInitVertexes = matched_subgraphs[j].getGroup(i);
					for (int k = 0; k < subInitVertexes.length; k++) {
						initVertexes.insert(subInitVertexes[k]);
					}
				}
				initVertexNums[i] = initVertexes.getCapacity();
				iterators[i] = new GroupIteratorInFullGraph(graph, initVertexes, vertexes, i);
			}
			fw.write("\r\n");
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
		
		Date s = new Date();
		initTime = s.getTime() - startTime;
	}

	public SimpleAnswer[] process(int k)  {
		startTime = new Date().getTime();
		
		int size = 0;
		SimpleAnswer[] topk = new SimpleAnswer[k];

		HashMap<Integer, double[]> allDistances = new HashMap<Integer, double[]>();
		HashMap<Integer, int[]> allPredecessors = new HashMap<Integer, int[]>();
		
		boolean firstk = true;
		boolean overBound = false;
		
		HashSet<Integer> abandoned = new HashSet<Integer>();
		HashSet<Integer> rest = new HashSet<Integer>();

		// begin to search
		while (!isEmpty()) {
			try {
				for (int i = 0; i < groupNum; i++) {
					if (!iterators[i].hasNext()) {
						groupEmpty[i] = true;
						continue;
					}
					
					SPVertex spv = iterators[i].next();
					
					int root = spv.getID();
					double distance = spv.getDistance();
					int predecessor = spv.getPredecessor();
					
					Integer R = new Integer(root);
					
					if (root == 108375) {
						System.out.println();
					}

					// maintaining predecessor records, which is always necessary
					if (!allPredecessors.containsKey(R)) {
						int[] predecessors = new int[groupNum];
						predecessors[i] = predecessor;
						allPredecessors.put(R, predecessors);
					}
					else {
						allPredecessors.get(R)[i] = predecessor;
					}
					
					if (abandoned.contains(R)) {
						continue;
					}
					
					double[] distances = allDistances.get(R);
					if (distances == null) {
						// arbitrary new root cannot hold a tree smaller than current topk
						if (overBound) {
							continue;
						}
						
						distances = new double[groupNum];
						distances[i] = distance;
						for (int j = 0; j < groupNum; j++) {
							if (j != i) {
								distances[j] = Double.MAX_VALUE;
							}
						}
						allDistances.put(R, distances);
						rest.add(R);
					}
					else {
						distances[i] = distance;
					}
					
					if (size == k && sumLBD(distances) > topk[k - 1].getScore()) {
						abandoned.add(R);
						rest.remove(R);
					}
					
					double sum = sumDistances(distances);
					if (sum != Double.MAX_VALUE) {
						if (size < k || sum < topk[k - 1].getScore()) {
							SimpleAnswer at = genAnswer(root, allPredecessors);
							size = addTopKAnswer(at, topk, size);
						}
						
						abandoned.add(R);
						rest.remove(R);
//						allDistances.remove(R);
						
						if (size == k) {
							if (firstk) {
								Date getFirstK = new Date();
								firstkTime = getFirstK.getTime() - startTime;
								try {
									if (needPrint) {
										fw.write("first-k answers:\r\n");
										double totalScore = 0.0d;
										for (int n = 0; n < topk.length; n++) {
											SimpleAnswer sa = topk[n];
											fw.write("Rank " + (n + 1) + ": {" + sa.getScore() + "} ");
											fw.write(" root[" + sa.getRoot() + "] ");
											totalScore += sa.getScore();
											for (int y = 0; y < sa.getLeafNumber(); y++) {
												int[] path = sa.getPath(y);
												fw.write("( ");
												if (path != null) {
													for (int m = 0; m < path.length; m++) {
														fw.write(path[m] + ", ");
													}
												}
												fw.write(" )");
											}
											fw.write("\r\n");
										}
										fw.write("Average score: " + (totalScore / k) + "\r\n");
										fw.write("\r\n");
									}
								}
								catch (IOException ex) {
									ex.printStackTrace();
								}
								startTime = new Date().getTime();
								
								firstk = false;
							}
						}
					}
					
					// check if algorithm can be stopped
					if (size < k) {
						continue;
					}
					if (!overBound) {
						double total = 0.0d;
						for (int j = 0; j < groupNum; j++) {
							total += iterators[j].peek();
						}
						if (total >= topk[k - 1].getScore()) {
							overBound = true;
						}
					}
					
					if (overBound) {
						boolean noSmallerTree = true;
						Iterator<Integer> vIt = rest.iterator();
						while (vIt.hasNext()) {
							Integer V = vIt.next();
							double[] dis = allDistances.get(V);
							double lowerBound = sumLBD(dis);
							if (lowerBound > topk[k - 1].getScore()) {
								abandoned.add(V);
								vIt.remove();
							}
							else {
								noSmallerTree = false;
								break;
							}
						}
//						Iterator<Integer> vIt = allDistances.keySet().iterator();
//						while (vIt.hasNext()) {
//							Integer V = vIt.next();
//							double[] dis = allDistances.get(V);
//							double lowerBound = 0.0d;
//							for (int j = 0; j < groupNum; j++) {
//								if (dis[j] < Double.MAX_VALUE) {
//									lowerBound += dis[j];
//								}
//								else {
//									try {
//										lowerBound += iterators[j].peek();
//									}
//									catch (UnderflowException ex) {
//										lowerBound = Double.MAX_VALUE;
//										break;
//									}
//								}
//							}
//							if (lowerBound >= topk[k - 1].getScore()) {
//								abandoned.add(V);
//								vIt.remove();
//							}
//							else {
//								noSmallerTree = false;
//							}
//						}
						
						if (noSmallerTree) {
							try {
								Date e = new Date();
								topkTime = e.getTime() - startTime;
								if (needPrint) {
									fw.write("top-k answers:\r\n");
									double sum2 = 0.0d;
									int n = 0;
									for (; n < topk.length; n++) {
										SimpleAnswer at = topk[n];
										if (at == null) {
											break;
										}
										fw.write("Rank " + (n + 1) + ": {" + at.getScore() + "} ");
										fw.write(" root[" + at.getRoot() + "] ");
										sum2 += at.getScore();
										for (int j = 0; j < at.getLeafNumber(); j++) {
											int[] path = at.getPath(j);
											fw.write("( ");
											if (path != null) {
												for (int m = 0; m < path.length; m++) {
													fw.write(path[m] + ", ");
												}
											}
											fw.write(" )");
										}
										fw.write("\r\n");
									}
									if (n == 0) {
										fw.write("Sorry, no result is found.\r\n");
									}
									else {
										fw.write("Average score: " + (sum2 / Math.min(k, n)) + "\r\n");
										fw.write("\r\n");
									}
								}
							}
							catch (IOException ex) {
								ex.printStackTrace();
							}
							System.out.println("Successfully stopped");
							return topk;
						}
					}
				}
			} 
			catch (UnderflowException ex) {
				ex.printStackTrace();
			}

		}
		try {
			Date e = new Date();
			topkTime = e.getTime() - startTime;
			if (needPrint) {
				fw.write("top-k answers:\r\n");
				double sum2 = 0.0d;
				int n = 0;
				for (; n < topk.length; n++) {
					SimpleAnswer at = topk[n];
					if (at == null) {
						break;
					}
					fw.write("Rank " + (n + 1) + ": {" + at.getScore() + "} ");
					fw.write(" root[" + at.getRoot() + "] ");
					sum2 += at.getScore();
					for (int j = 0; j < at.getLeafNumber(); j++) {
						int[] path = at.getPath(j);
						fw.write("( ");
						if (path != null) {
							for (int m = 0; m < path.length; m++) {
								fw.write(path[m] + ", ");
							}
						}
						fw.write(" )");
					}
					fw.write("\r\n");
				}
				if (n == 0) {
					fw.write("Sorry, no result is found.\r\n");
				}
				else {
					fw.write("Average score: " + (sum2 / Math.min(k, n)) + "\r\n");
					fw.write("\r\n");
				}
			}
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
		System.out.println("All processed");
		return topk;
	}
	
	private boolean isEmpty() {
		for (int i = 0; i < groupNum; i++) {
			if (!groupEmpty[i]) {
				return false;
			}
		}
		return true;
	}
	
	private double sumDistances(double[] distances) {
		double sum = 0.0d;
		for (int j = 0; j < groupNum; j++) {
			if (distances[j] == Double.MAX_VALUE) {
				return Double.MAX_VALUE;
			}
			else {
				sum += distances[j];
			}
		}
		return sum;
	}
	
	private double sumLBD(double[] distances) throws UnderflowException {
		double sum = 0.0d;
		for (int j = 0; j < groupNum; j++) {
			if (distances[j] == Double.MAX_VALUE) {
				if (iterators[j].hasNext()) {
					sum += iterators[j].peek();
				}
				else {
					return Double.MAX_VALUE;
				}
			}
			else {
				sum += distances[j];
			}
		}
		return sum;
	}
	
	private SimpleAnswer genAnswer(int root, HashMap<Integer, int[]> allPredecessors) {
		int[] leaves = new int[groupNum];
		int[][] paths = new int[groupNum][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		
		for (int i = 0; i < groupNum; i++) {
			paths[i] = getPath(root, i, allVertexes, 
					allPredecessors);
			if (paths[i] == null) {
				leaves[i] = root;
			}
			else {
				leaves[i] = paths[i][paths[i].length - 1];
			}
		}
		
		return new SimpleAnswer(root, leaves, paths, allVertexes.getArray());
	}

	private int[] getPath(int root, int i,
			SequentialIntArray allVertexes, HashMap<Integer, int[]> allPredecessors) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;
		
		do {
			current = allPredecessors.get(new Integer(current))[i];
			if (current == 0) {
				System.err.println("Error: predecessor not found");
				System.exit(1);
			}
			else if (current != -1) {
				allVertexes.insert(current);
				eia.add(current);
			}
			else {
				break;
			}
		} while (true);
		
		return eia.toArray();
	}
	
	private int addTopKAnswer(SimpleAnswer answer, SimpleAnswer[] topk, int size) {
		int pos = -1;
		boolean inserted = false;
		for (int i = 0; i < size; i++) {
			int x = answer.compare(topk[i]);
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return size;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				if (!inserted) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					inserted = true;
				}
				else {
					for (int j = i; j < size - 1; j++) {
						topk[j] = topk[j + 1];
					}
					size--;
				}
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < topk[i].getScore()) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					return size;
				}
				else {
					return size;
				}
			}
			
			if (answer.getScore() >= topk[i].getScore()) {
				pos = i;
			}
		}
		
		if (inserted) {
			return size;
		}
		
		if (pos < size - 1) {
			if (size < topk.length) {
				for (int i = size; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
				size++;
			}
			else {
				for (int i = topk.length - 1; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
			}
			topk[pos + 1] = answer;
		}
		else if (size < topk.length) {
			topk[size] = answer;
			size++;
		}
		
		return size;
	}

}
